package org.example.util;

/**
 * @ClassName JumpPointSearch
 * @Description TODO
 * @Author hongjun
 * @Date 2024/5/10 下午11:56
 * @Version 1.0
 */
import java.util.*;

import java.util.*;

public class JumpPointSearch {
    private static final int[][] DIRECTIONS = {
            {1, 0}, {0, 1}, {-1, 0}, {0, -1}, // Cardinal directions
            {1, 1}, {-1, 1}, {-1, -1}, {1, -1}  // Diagonal directions
    };

    public static List<int[]> jumpPointSearch(int[][] map, int startX, int startY, int endX, int endY) {
        LinkedList<int[]> openList = new LinkedList<>();
        Set<String> closedList = new HashSet<>();
        int[][] cameFromX = new int[map.length][map[0].length];
        int[][] cameFromY = new int[map.length][map[0].length];
        int[][] gScore = new int[map.length][map[0].length];
        for (int[] row : gScore) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        openList.add(new int[]{startX, startY, 0});
        gScore[startX][startY] = 0;

        while (!openList.isEmpty()) {
            int[] current = openList.removeFirst();
            int x = current[0];
            int y = current[1];
            int currentGScore = current[2];

            String key = x + "," + y;
            if (closedList.contains(key)) {
                continue;
            }
            closedList.add(key);

            if (x == endX && y == endY) {
                return reconstructPath(cameFromX, cameFromY, endX, endY);
            }

            for (int[] direction : DIRECTIONS) {
                int newX = x + direction[0];
                int newY = y + direction[1];

                if (newX < 0 || newX >= map.length || newY < 0 || newY >= map[0].length || map[newX][newY] == 1) {
                    continue;
                }

                if (jump(map, x, y, newX, newY, direction)) {
                    int tentativeGScore = currentGScore + ((direction[0] == 0 || direction[1] == 0) ? 1 : 2);
                    if (tentativeGScore < gScore[newX][newY]) {
                        cameFromX[newX][newY] = x;
                        cameFromY[newX][newY] = y;
                        gScore[newX][newY] = tentativeGScore;
                        openList.add(new int[]{newX, newY, tentativeGScore});
                    }
                }
            }
        }
        return null;
    }
    private static boolean jump(int[][] map, int x, int y, int newX, int newY, int[] direction) {
        if (x == newX || y == newY) { // Cardinal move
            return true;
        }
        // Diagonal move
        int dx = direction[0];
        int dy = direction[1];
        int nx, ny;
        if (!((newX > x) ^ (dx < 0))) return false; // Moving in wrong horizontal direction
        if (!((newY > y) ^ (dy < 0))) return false; // Moving in wrong vertical direction
        nx = x + dx;
        ny = y;
        if (canMove(map, nx, ny) && !jump(map, nx, ny, newX, newY, new int[]{dx, 0})) return false;
        nx = x;
        ny = y + dy;
        if (canMove(map, nx, ny) && !jump(map, nx, ny, newX, newY, new int[]{0, dy})) return false;
        return true;
    }

    private static boolean canMove(int[][] map, int x, int y) {
        return x >= 0 && x < map.length && y >= 0 && y < map[0].length && map[x][y] == 0;
    }

    // ... (jump and canMove methods remain the same)

    private static List<int[]> reconstructPath(int[][] cameFromX, int[][] cameFromY, int endX, int endY) {
        LinkedList<int[]> path = new LinkedList<>();
        while (endX != -1 || endY != -1) {
            path.addFirst(new int[]{endX, endY});
            endX = cameFromX[endX][endY];
            endY = cameFromY[endX][endY];
        }
        return path;
    }
}
